package org.xingole.daily;

/**
 * <a href="https://leetcode.com/problems/minimum-number-of-increments-on-subarrays-to-form-a-target-array/description/">
 * Problem Description
 * </a>
 * 
 * <h3>
 * How can we prove the following approach is correct ?
 * 
 * <p>
 * A more intuitive proof is to consider each number in the array target from left to right,
 * similar to the concept of a <strong>monotonic stack</strong>.
 * 
 * <p>
 * For target[0], the minimum number operations required is simply <code>target[0]</code>.
 * For two adjacent numbers <code>target[i]</code> and <code>target[i+1]</code>:
 * 
 * <ul>
 *      <li>If <code>target[i] >= target[i+1]</code>, then when we increase target[i] by 1, we can simultaneously
 * increase <code>target[i+1]</code> by 1 as well. Therefore, <code>target[i+1]</code> does not require any
 * additional operations.
 *      <li>If <code>target[i] < target[i+1]</code>, then even after increasing both by 1, we still need
 * an additional <code>target[i+1]-target[i]</code> operations to reach the correct result.
 * </ul>
 * 
 * <p>
 * Thus we can obtain the minimum number of operations as:
 * <pre>
 *      target[0] + sum(max{target[i+1]-target[i], 0}) for i = 0, ..., n-2
 * </pre>
 * 
 * <h3>
 * Approach 2: Difference Array
 * 
 * <p>
 * <a href="https://leetcode.cn/problems/minimum-number-of-increments-on-subarrays-to-form-a-target-array/solutions/371326/xing-cheng-mu-biao-shu-zu-de-zi-shu-zu-zui-shao-ze/">
 * Proof</a>
 */
public class MinimumNumberOfIncrementsOnSubarraysToFromATargetArray {

    public int minNumberOperations(int[] target) {
        // This problem can be solved in only five lines of code:
        // Calculate the difference between adjacent elements in the array
        // target, keep only the positive parts, and sum them up as the answer.
        int n = target.length;
        int ans = target[0];
        for (int i = 1; i < n; ++i) {
            ans += Math.max(target[i] - target[i - 1], 0);
        }

        return ans;
    }
}
